{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K Radius Subarray Averages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getAverages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #半径为 k 的子数组平均值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的数组 <code>nums</code> ，数组中有 <code>n</code> 个整数，另给你一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p><strong>半径为 k 的子数组平均值</strong> 是指：<code>nums</code> 中一个以下标 <code>i</code> 为 <strong>中心</strong> 且 <strong>半径</strong> 为 <code>k</code> 的子数组中所有元素的平均值，即下标在&nbsp;<code>i - k</code> 和 <code>i + k</code> 范围（<strong>含</strong> <code>i - k</code> 和 <code>i + k</code>）内所有元素的平均值。如果在下标 <code>i</code> 前或后不足 <code>k</code> 个元素，那么<strong> 半径为 k 的子数组平均值 </strong>是 <code>-1</code> 。</p>\n",
    "\n",
    "<p>构建并返回一个长度为 <code>n</code> 的数组<em> </em><code>avgs</code><em> </em>，其中<em> </em><code>avgs[i]</code><em> </em>是以下标 <code>i</code> 为中心的子数组的<strong> 半径为 k 的子数组平均值 </strong>。</p>\n",
    "\n",
    "<p><code>x</code> 个元素的 <strong>平均值</strong> 是 <code>x</code> 个元素相加之和除以 <code>x</code> ，此时使用截断式 <strong>整数除法</strong> ，即需要去掉结果的小数部分。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，四个元素 <code>2</code>、<code>3</code>、<code>1</code> 和 <code>5</code> 的平均值是 <code>(2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75</code>，截断后得到 <code>2</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/07/eg1.png\" style=\"width: 343px; height: 119px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [7,4,3,9,1,8,5,2,6], k = 3\n",
    "<strong>输出：</strong>[-1,-1,-1,5,4,4,-1,-1,-1]\n",
    "<strong>解释：</strong>\n",
    "- avg[0]、avg[1] 和 avg[2] 是 -1 ，因为在这几个下标前的元素数量都不足 k 个。\n",
    "- 中心为下标 3 且半径为 3 的子数组的元素总和是：7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。\n",
    "  使用截断式 <strong>整数除法</strong>，avg[3] = 37 / 7 = 5 。\n",
    "- 中心为下标 4 的子数组，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。\n",
    "- 中心为下标 5 的子数组，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。\n",
    "- avg[6]、avg[7] 和 avg[8] 是 -1 ，因为在这几个下标后的元素数量都不足 k 个。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [100000], k = 0\n",
    "<strong>输出：</strong>[100000]\n",
    "<strong>解释：</strong>\n",
    "- 中心为下标 0 且半径 0 的子数组的元素总和是：100000 。\n",
    "  avg[0] = 100000 / 1 = 100000 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [8], k = 100000\n",
    "<strong>输出：</strong>[-1]\n",
    "<strong>解释：</strong>\n",
    "- avg[0] 是 -1 ，因为在下标 0 前后的元素数量均不足 k 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i], k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-radius-subarray-averages](https://leetcode.cn/problems/k-radius-subarray-averages/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-radius-subarray-averages](https://leetcode.cn/problems/k-radius-subarray-averages/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,4,3,9,1,8,5,2,6]\\n3', '[100000]\\n0', '[8]\\n100000']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def getAverages(self, nums, k):\n",
    "            n = len(nums)\n",
    "            ans = [-1] * n\n",
    "            length = 2 * k + 1\n",
    "            if length > n:\n",
    "                return ans\n",
    "\n",
    "            total_sum = sum(nums[:length])\n",
    "            ans[k] = total_sum // length\n",
    "            start = 0\n",
    "            for last in range(length, n):\n",
    "                total_sum = total_sum - nums[start] + nums[last]\n",
    "                start += 1\n",
    "                ans[last - k] = total_sum // length\n",
    "\n",
    "            return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        lenth = len(nums)\n",
    "        k2 = k * 2 + 1  # 子数组长度\n",
    "        if lenth < k2:\n",
    "            return [-1] * lenth\n",
    "        else:\n",
    "            s = sum(nums[:k2])\n",
    "        ans = [0] * lenth\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            if i < k or i >= lenth - k:\n",
    "                ans[i] = -1\n",
    "            elif i != k:\n",
    "                s += nums[i+k] - nums[i-k-1]\n",
    "                ans[i] = s // k2\n",
    "            else:\n",
    "                ans[i] = s // k2\n",
    "                \n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        curr = 0\n",
    "        for i in range(n):\n",
    "            curr += nums[i]\n",
    "            if i >= 2*k:\n",
    "                res[i-k] = curr//(2*k+1)\n",
    "                curr -= nums[i-2*k]\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        k2 = k * 2 + 1  # 子数组长度\n",
    "        ans = [-1] * n\n",
    "        if n >= k2:\n",
    "            s = sum(nums[:k2])\n",
    "            ans[k] = s // k2\n",
    "            for i in range(k + 1, n - k):\n",
    "                s += nums[i+k] - nums[i-k-1]\n",
    "                ans[i] = s // k2\n",
    "                \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ret=[-1]*n\n",
    "        avg=0\n",
    "        if 2*k+1>n: return ret\n",
    "        avg=sum(nums[:2*k+1])\n",
    "        ret[k]=avg//(2*k+1)\n",
    "        for i in range(k+1,n-k):\n",
    "            avg=avg-nums[i-k-1]+nums[i+k]\n",
    "            ret[i]=avg//(2*k+1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = [-1] * len(nums)\n",
    "        sums = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            sums +=x\n",
    "            if i < k:\n",
    "                continue\n",
    "            if i >=k*2:\n",
    "                ans[i-k] = sums//(2*k+1)\n",
    "                sums-= nums[i-2*k]\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        lst=[-1]*n\n",
    "        if n==2*k+1:\n",
    "            lst[k]=sum(nums)//n\n",
    "        elif n>2*k+1:\n",
    "            x0=sum(nums[:2*k+1])\n",
    "            lst[k]=x0//(2*k+1)\n",
    "            for i in range(k,n-k-1):\n",
    "                x0=x0+nums[i+k+1]-nums[i-k]\n",
    "                lst[i+1]=x0//(2*k+1)\n",
    "        return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        lenth = len(nums)\n",
    "        k2 = k * 2 + 1  # 子数组长度\n",
    "        if lenth < k2:\n",
    "            return [-1] * lenth\n",
    "        else:\n",
    "            s = sum(nums[:k2])\n",
    "        ans = [0] * lenth\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            if i < k or i >= lenth - k:\n",
    "                ans[i] = -1\n",
    "            else:\n",
    "                if i != k:\n",
    "                    s += nums[i+k] - nums[i-k-1]\n",
    "                ans[i] = s // k2\n",
    "                \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n\n",
    "        cnt = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            cnt += x\n",
    "            if i < n and i >= 2*k:\n",
    "                ans[i-k] = cnt//(2*k+1)\n",
    "                cnt -= nums[i-2*k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        if len(nums)<2*k+1:\n",
    "            return [-1]*len(nums)\n",
    "        \n",
    "        res=[-1]*len(nums)\n",
    "        s1=sum(nums[:2*k+1])\n",
    "        res[k]=s1//(2*k+1)\n",
    "        for e in range(2*k+1,len(nums)):\n",
    "            s1+=nums[e]-nums[e-(2*k+1)]\n",
    "            res[e-k]=s1//(2*k+1)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        \n",
    "        res=[-1]*n\n",
    "        \n",
    "        if k==0:\n",
    "                diff=1\n",
    "        else:\n",
    "            diff=2*k+1\n",
    "        if n<diff:\n",
    "            return res\n",
    "        temp=sum(nums[:2*k+1])\n",
    "        res[k]=temp//diff\n",
    "        for i in range(k+1,n-k):\n",
    "            temp+=nums[i+k]-nums[i-k-1]\n",
    "            \n",
    "            res[i]=temp//diff\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        # length: 2* k+ 1\n",
    "        total = 0\n",
    "        start = 0\n",
    "        n = len(nums)\n",
    "        if k == 0:\n",
    "            return nums\n",
    "        res = [-1] * n\n",
    "        if 2*k + 1 > n:\n",
    "            return res\n",
    "        for end in range(n):\n",
    "            total += nums[end]\n",
    "            if start < n and end - start + 1 > 2*k + 1:\n",
    "                total -= nums[start]\n",
    "                start += 1 # start +=1\n",
    "\n",
    "            if end - start + 1 == 2* k + 1:\n",
    "                res[(start + end)//2] = total//(2*k+1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=[-1]*n\n",
    "        if k*2>=n:\n",
    "            return ans\n",
    "        #枚举中心点\n",
    "        lent=2*k+1\n",
    "        total=sum(nums[:2*k])\n",
    "        for i in range(k,n-k):\n",
    "            total+=nums[i+k]\n",
    "            ans[i]=int(total/lent)\n",
    "            total-=nums[i-k]       \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        if not k:\n",
    "            return nums\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        x = k*2+1\n",
    "        if n < x:\n",
    "            return ans\n",
    "        total = sum(nums[:x])\n",
    "        ans[k] = total // x\n",
    "        for i in range(x, n):\n",
    "            total += nums[i] - nums[i-x]\n",
    "            ans[i-k] = total // x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        acc = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            if i - k < 0 or i +k >= n: \n",
    "                ans[i] = -1\n",
    "            acc += v\n",
    "            if i >= k * 2:\n",
    "                ans[i-k] = acc // (2*k+1)\n",
    "                acc -= nums[i-k*2]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        lenth = len(nums)\n",
    "        k2 = k * 2 + 1  # 子数组长度\n",
    "        if lenth < k2:\n",
    "            return [-1] * lenth\n",
    "        else:\n",
    "            s = sum(nums[:k2])\n",
    "        ans = [0] * lenth\n",
    "\n",
    "        for i in range(lenth):\n",
    "            if i < k or i >= lenth - k:\n",
    "                ans[i] = -1\n",
    "            elif i != k:\n",
    "                s += nums[i+k] - nums[i-k-1]\n",
    "                ans[i] = s // k2\n",
    "            else:\n",
    "                ans[i] = s // k2\n",
    "                \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        slide_len = k * 2 + 1\n",
    "        n = len(nums)\n",
    "        res = [-1] * n\n",
    "        if n < slide_len: return res\n",
    "        slide_sum = sum(nums[:slide_len])\n",
    "        res[k] = slide_sum // slide_len\n",
    "        for i in range(slide_len, n):\n",
    "            slide_sum += nums[i] - nums[i - slide_len]\n",
    "            res[i-k] = slide_sum // slide_len\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n\n",
    "        if n < 2*k+1:\n",
    "            return ans\n",
    "        cnt = sum(nums[:2*k])\n",
    "        for i,(out_,in_) in enumerate(zip(nums,nums[2*k:])):\n",
    "            cnt += in_\n",
    "            ans[k+i] = cnt//(2*k+1)\n",
    "            cnt -= out_\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        l, r = 0, 2 * k\n",
    "        res = [-1] * n \n",
    "        mid = k\n",
    "        if r >= n:\n",
    "            return res\n",
    "        windowSum = sum(nums[:r])\n",
    "\n",
    "        while r < n:\n",
    "            windowSum += nums[r]\n",
    "            r += 1\n",
    "            res[mid] = windowSum // (2*k+1)\n",
    "            mid += 1\n",
    "            windowSum -= nums[l]\n",
    "            l += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n\n",
    "        if n < 2*k+1:\n",
    "            return ans\n",
    "        cnt = sum(nums[:2*k])\n",
    "        for i,(out_,in_) in enumerate(zip(nums,nums[2*k:])):\n",
    "            cnt += in_\n",
    "            ans[k+i] = cnt//(2*k+1)\n",
    "            cnt -= out_\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        if 2*k>=n:\n",
    "            return [-1]*n\n",
    "        s=sum(nums[:2*k+1])\n",
    "        ans=[-1]*k+[s//(2*k+1)]\n",
    "        for i in range(n-2*k-1):\n",
    "            s-=nums[i]\n",
    "            s+=nums[i+2*k+1]\n",
    "            ans.append(s//(2*k+1))\n",
    "        return ans+[-1]*k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        if k == 0:\n",
    "            return nums\n",
    "        left, mid, right = 0, 0, k\n",
    "\n",
    "        res = []\n",
    "\n",
    "        win_sum = sum(nums[:k])\n",
    "\n",
    "        while mid < len(nums):\n",
    "            mid += 1\n",
    "            if right < len(nums):\n",
    "                c = nums[right]\n",
    "                right += 1\n",
    "\n",
    "                win_sum += c\n",
    "            # print(left, mid, right, win_sum)\n",
    "\n",
    "            if k < mid <= len(nums) - k:\n",
    "                tmp = win_sum // (2 * k + 1)\n",
    "\n",
    "\n",
    "                d = nums[left]\n",
    "                left += 1\n",
    "\n",
    "\n",
    "                win_sum -= d\n",
    "            else:\n",
    "                tmp = -1\n",
    "\n",
    "            res.append(tmp)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n, k2 = len(nums), (k * 2) + 1\n",
    "        if n < k2: return [-1] * n\n",
    "        sum_ = sum(nums[: k2])\n",
    "        ans = [sum_ // k2]\n",
    "        for i in range(k + 1, n - k):\n",
    "            sum_ += nums[i + k] - nums[i - k - 1]\n",
    "            ans.append(sum_ // k2)\n",
    "        return [-1] * k + ans + [-1] * k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        pre_sum = 0\n",
    "        if k == 0:\n",
    "            return nums\n",
    "        if k > n:\n",
    "            return [-1]*n\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            pre_sum += nums[i]\n",
    "            if i < k:\n",
    "                ans.append(-1)\n",
    "            if i >= 2*k:\n",
    "                if i > 2*k:\n",
    "                    pre_sum -= nums[i-2*k-1]\n",
    "                ans.append(pre_sum// (2*k + 1))\n",
    "        return ans + [-1]*(n-len(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        m = 2 * k + 1\n",
    "        ans = [-1] * len(nums)\n",
    "        total = sum(nums[:m-1])\n",
    "\n",
    "        for i in range(m-1, len(nums)):\n",
    "            total += nums[i]\n",
    "            ans[i-k] = total // m\n",
    "            total -= nums[i-m+1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n \n",
    "        s = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            s += x\n",
    "            if i >= k * 2:\n",
    "                ans[i - k] = s // (2 * k + 1)\n",
    "                s -= nums[i - k * 2]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n\n",
    "        m = 2*k+1\n",
    "        cur = sum(nums[:2*k+1])\n",
    "        if 2*k<n:\n",
    "            ans[k] = cur//m\n",
    "        for i in range(k+1,n-k):\n",
    "            cur+=nums[i+k]-nums[i-k-1]\n",
    "            ans[i] = cur//m\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        avg = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i < k or i > (len(nums) - 1 - k):\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                if i == k:\n",
    "                    avg_sum = sum(nums[i - k:i + k + 1])\n",
    "\n",
    "                else:\n",
    "                    print(i)\n",
    "                    avg_sum = avg_sum + nums[i+k] - nums[i-k-1]\n",
    "\n",
    "                res.append(int(avg_sum / (2 * k + 1)))\n",
    "                #print(nums[i-k:i+k-1])\n",
    "                #res.append(int(sum(nums[i-k:i+k+1])/(2*k+1)))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ret=[-1]*n\n",
    "        avg=0\n",
    "        if 2*k+1>n: return ret\n",
    "        for d in range(2*k+1):\n",
    "             avg=avg+nums[d]\n",
    "        ret[k]=avg//(2*k+1)\n",
    "        for i in range(k+1,n-k):\n",
    "            avg=avg-nums[i-k-1]+nums[i+k]\n",
    "            ret[i]=avg//(2*k+1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        #初始化数组的长度和半径为k的子数组总长度\n",
    "        n, k2 = len(nums), (k * 2) + 1\n",
    "        if n < k2: return [-1] * n\n",
    "        sum_a = sum(nums[: k2])\n",
    "        ans = [sum_a // k2]\n",
    "        for i in range(k + 1, n - k):\n",
    "            sum_a += nums[i + k] - nums[i - k - 1]\n",
    "            ans.append(sum_a // k2)\n",
    "        return [-1] * k + ans + [-1] * k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        l, res = 0, [-1] * n\n",
    "        total = sum(nums[: 2 * k])\n",
    "        for r in range(k, n - k):\n",
    "            total += nums[r + k]\n",
    "            res[r] = total // (2 * k + 1)\n",
    "            total -= nums[r - k]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        gap = 2 * k + 1\n",
    "        if n < gap:\n",
    "            return ans\n",
    "        for i in range(gap):\n",
    "            ans[k] += nums[i]\n",
    "        tmp = ans[k] + 1\n",
    "        ans[k] = tmp // gap\n",
    "        for i in range(gap,n):\n",
    "            tmp += nums[i] - nums[i - gap]\n",
    "            ans[i - k] = tmp // gap\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        if len(nums)<2*k+1:\n",
    "            return [-1]*len(nums)\n",
    "        res = [-1]*k\n",
    "        sum1 = sum(nums[:2*k+1])\n",
    "        mod = 2*k+1\n",
    "        res.append(sum1//mod)\n",
    "        j = 0\n",
    "        for i in range(2*k+1,len(nums)):\n",
    "            sum1 +=nums[i]\n",
    "            sum1 -= nums[j]\n",
    "            j+=1\n",
    "            res.append(sum1//mod)\n",
    "        res += [-1]*k\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        p1 = 0\n",
    "        p2 = 2*k\n",
    "        temp = sum(nums[:p2+1])\n",
    "        while p2 < n:\n",
    "            ans[p1+k] = temp // (2*k+1)\n",
    "            temp -= nums[p1]\n",
    "            p1 += 1\n",
    "            p2 += 1\n",
    "            if p2 < n:\n",
    "                temp += nums[p2]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        movingAvgs = [-1] * len(nums)\n",
    "        curSum = 0\n",
    "        winSize = 2 * k + 1\n",
    "\n",
    "        for endIdx, num in enumerate(nums):\n",
    "            curSum += num\n",
    "            startIdx = endIdx - winSize + 1\n",
    "            if startIdx < 0:\n",
    "                continue\n",
    "            curAvg = curSum // winSize\n",
    "            movingAvgs[endIdx - k] = curAvg\n",
    "            curSum -= nums[startIdx]\n",
    "\n",
    "        return movingAvgs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        avg = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i < k or i > (len(nums) - 1 - k):\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                if i == k:\n",
    "                    avg_sum = sum(nums[i - k:i + k + 1])\n",
    "\n",
    "                else:\n",
    "                    print(i)\n",
    "                    avg_sum = avg_sum + nums[i+k] - nums[i-k-1]\n",
    "\n",
    "                res.append(int(avg_sum / (2 * k + 1)))\n",
    "                #print(nums[i-k:i+k-1])\n",
    "                #res.append(int(sum(nums[i-k:i+k+1])/(2*k+1)))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        lenth = len(nums)\n",
    "        k2 = k * 2 + 1  # 子数组长度\n",
    "        if lenth < k2:\n",
    "            return [-1] * lenth\n",
    "        else:\n",
    "            s = sum(nums[:k2])\n",
    "        ans = [-1] * k + [s // k2] + [0] * (lenth - k2) + [-1] * k\n",
    "\n",
    "        for i in range(k + 1, lenth - k):\n",
    "            s += nums[i+k] - nums[i-k-1]\n",
    "            ans[i] = s // k2\n",
    "                \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = [-1]*k\n",
    "        n = len(nums)\n",
    "        if n < 2*k:\n",
    "            return [-1]*n\n",
    "        # 滑动窗口优化求和过程\n",
    "        window = sum(nums[:2*k+1])\n",
    "        for i in range(k,n-k):\n",
    "            res.append(window//(2*k+1))\n",
    "            if i != n-k-1:\n",
    "                window += nums[i+k+1]\n",
    "                window -= nums[i-k]\n",
    "        res.extend([-1]*(k))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "      n = len(nums)\n",
    "      avg = [-1] * n\n",
    "      sums = 0\n",
    "      if 2*k +1> n:\n",
    "        return avg\n",
    "      for i in range(2*k+1):\n",
    "        sums += nums[i]\n",
    "      avg[k] = sums // (2*k +1)\n",
    "      for i in range(k+1,n-k):\n",
    "        sums += nums[i+k] - nums[i-k-1]\n",
    "        avg[i] = sums // (2*k +1)\n",
    "      \n",
    "      return avg\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        if k * 2 + 1 <= n:\n",
    "            total = sum(nums[:k * 2 + 1])\n",
    "            for i in range(k, n - k):\n",
    "                if i != k:\n",
    "                    total += nums[i + k] - nums[i - k - 1]\n",
    "                ans[i] = total // (k * 2 + 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        if k * 2 + 1 <= n:\n",
    "            acc = sum(nums[:k * 2 + 1])\n",
    "            for i in range(k, n - k):\n",
    "                if i != k:\n",
    "                    acc += nums[i + k] - nums[i - k - 1]\n",
    "                ans[i] = acc // (k * 2 + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        if k * 2 + 1 <= n:\n",
    "            total = sum(nums[:k * 2 + 1])\n",
    "            for i in range(k, n - k):\n",
    "                if i != k:\n",
    "                    total += nums[i + k] - nums[i - k - 1]\n",
    "                ans[i] = total // (k * 2 + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1]*n\n",
    "        if k*2+1 <= n:\n",
    "            tot = sum(nums[:k*2+1])\n",
    "            for i in range(k,n-k):\n",
    "                if i != k:\n",
    "                    tot += nums[i+k]-nums[i-k-1]\n",
    "                ans[i] = tot//(2*k+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = [-1]*len(nums)\n",
    "        pre = list(accumulate(nums,initial=0))\n",
    "        for i in range(k,len(nums)-k):\n",
    "            ans[i] = (pre[i+k+1]-pre[i-k])//(2*k+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        if k * 2 + 1 <= n:\n",
    "            total = sum(nums[:k * 2 + 1])\n",
    "            for i in range(k, n - k):\n",
    "                if i != k:\n",
    "                    total += nums[i + k] - nums[i - k -1]\n",
    "                ans[i] = total // (k * 2 + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        if k * 2 + 1 <= n:\n",
    "            total = sum(nums[:k*2 + 1])\n",
    "            for i in range(k, n-k):\n",
    "                if i != k:\n",
    "                    total += nums[i+k] - nums[i-k-1]\n",
    "                ans[i] = total // (k*2 + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        diameter = 2 * k + 1\n",
    "        if n < diameter:\n",
    "            return [-1] * n\n",
    "        cur_sum = sum(nums[:diameter])\n",
    "        res = []\n",
    "        res.append(cur_sum // diameter)\n",
    "        for i in range(k+1, n-k):\n",
    "            cur_sum += nums[i+k] - nums[i-k-1]\n",
    "            res.append(cur_sum // diameter)\n",
    "        return [-1] * k + res + [-1] * k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        lenth = len(nums)\n",
    "        k2 = k * 2 + 1  # 子数组长度\n",
    "        if lenth < k2:\n",
    "            return [-1] * lenth\n",
    "        else:\n",
    "            s = sum(nums[:k2])\n",
    "        ans = [-1] * k + [0] * (lenth - k * 2) + [-1] * k\n",
    "\n",
    "        for i in range(k, lenth-k):\n",
    "            if i != k:\n",
    "                s += nums[i+k] - nums[i-k-1]\n",
    "            ans[i] = s // k2\n",
    "                \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ret = [-1] * n\n",
    "        if n < k << 1 | 1:\n",
    "            return ret\n",
    "        s = 0\n",
    "        for i in range(k << 1| 1):\n",
    "            s += nums[i]\n",
    "        ret[k] = s // (k  << 1| 1)\n",
    "        for i in range( k << 1| 1, n):\n",
    "            s += nums[i] - nums[i - 2 * k - 1]\n",
    "            # print(i, i - 2 * k - 1, s)\n",
    "            ret[i - k] = s // ( k  << 1| 1)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        i, ans, cnt = 0, [-1 for _ in range(n)], 0\n",
    "        if n < 2 * k + 1:\n",
    "            return ans\n",
    "        for j, x in enumerate(nums):\n",
    "            cnt += x\n",
    "            if j >= k:\n",
    "                if j - i + 1 > k * 2 + 1:\n",
    "                    cnt -= nums[i]\n",
    "                    i += 1\n",
    "                if j - i + 1 == k * 2 + 1:\n",
    "                    ans[(j + i) >> 1] = cnt // (k * 2 + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        i, ans, cnt = 0, [-1 for _ in range(n)], 0\n",
    "        if n < 2 * k + 1:\n",
    "            return ans\n",
    "        for j, x in enumerate(nums):\n",
    "            cnt += x\n",
    "            if j >= k:\n",
    "                if j - i + 1 > k * 2 + 1:\n",
    "                    cnt -= nums[i]\n",
    "                    i += 1\n",
    "                if j - i + 1 == k * 2 + 1:\n",
    "                    ans[(j + i) >> 1] = cnt // (k * 2 + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        i, ans, cnt = 0, [-1 for _ in range(n)], 0\n",
    "        if n < 2 * k + 1:\n",
    "            return ans\n",
    "        for j, x in enumerate(nums):\n",
    "            cnt += x\n",
    "            if j >= k:\n",
    "                if j - i + 1 > k * 2 + 1:\n",
    "                    cnt -= nums[i]\n",
    "                    i += 1\n",
    "                if j - i + 1 == k * 2 + 1:\n",
    "                    ans[(j + i) >> 1] = cnt // (k * 2 + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        K = k*2+1\n",
    "        if n < K:\n",
    "            return [-1 for _ in nums]\n",
    "        k数组和 = sum(nums[:k*2])\n",
    "        返回 = [-1]*n\n",
    "        for i in range(k, n-k):\n",
    "            k数组和 += nums[i+k]\n",
    "            返回[i] = k数组和//K\n",
    "            k数组和 -= nums[i-k]\n",
    "        return 返回\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        l,cnt,t = 0,0,2*k+1\n",
    "        ans = [-1]*len(nums)\n",
    "        for r,s in enumerate(nums):\n",
    "            cnt += s\n",
    "            while r-l+1 > t:\n",
    "                cnt -= nums[l]\n",
    "                l += 1\n",
    "            if r-l+1 >= t:\n",
    "                #ans.append(int(cnt/t))\n",
    "                ans[l+k] = int(cnt/t)\n",
    "                #print(f'{nums[l:r+1]} = {cnt} {t} {int(cnt/t)}')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        left=0\n",
    "        s=0\n",
    "        n=len(nums)\n",
    "        ans=[-1]*n\n",
    "        for right,x in enumerate(nums):\n",
    "            s+=x\n",
    "            while right-left==2*k:\n",
    "                ans[(right+left)//2]=s//(2*k+1)\n",
    "                s-=nums[left]\n",
    "                left+=1\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        i, ans, cnt = 0, [-1 for _ in range(n)], 0\n",
    "        if n < 2 * k + 1:\n",
    "            return ans\n",
    "        for j, x in enumerate(nums):\n",
    "            cnt += x\n",
    "            if j >= k:\n",
    "                if j - i + 1 > k * 2 + 1:\n",
    "                    cnt -= nums[i]\n",
    "                    i += 1\n",
    "                if j - i + 1 == k * 2 + 1:\n",
    "                    ans[(j + i) >> 1] = cnt // (k * 2 + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        if len(nums) >= 2*k+1:\n",
    "            cursum = sum(nums[:2*k+1])\n",
    "        for i in range(len(nums)):\n",
    "            if i<k or i+k>=len(nums):\n",
    "                res.append(-1)\n",
    "                continue\n",
    "            \n",
    "            if i>k:\n",
    "                cursum += nums[i+k]\n",
    "                cursum -= nums[i-k-1]\n",
    "            res.append(cursum//(2*k+1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        length=len(nums)\n",
    "        if k*2+1>length:\n",
    "            return [-1]*length\n",
    "        result=[]\n",
    "        sum=0\n",
    "        for i in range(0,k*2+1):\n",
    "            sum+=nums[i]\n",
    "        for i in range(0,length):\n",
    "            if i<k or i+k>=length:\n",
    "                result.append(-1)\n",
    "                continue\n",
    "            elif i!=k:\n",
    "                sum+=nums[i+k]\n",
    "                sum-=nums[i-k-1]\n",
    "            result.append(floor(sum/(2*k+1)))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        n = len(nums)\n",
    "        res = [-1 for i in range(n)]\n",
    "        window = k*2+1\n",
    "\n",
    "        if n < window:\n",
    "            return res\n",
    "        else:\n",
    "            total_sum = sum(nums[:window])\n",
    "            for i in range(k, n):\n",
    "                res[i] = total_sum//window\n",
    "                total_sum -= nums[i-k]\n",
    "                if i+k+1 < n:\n",
    "                    total_sum += nums[i+k+1]\n",
    "                else:\n",
    "                    break\n",
    "        return res\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        K = k*2+1\n",
    "        if n < K:\n",
    "            return [-1 for _ in nums]\n",
    "        k数组和 = sum(nums[:k*2])\n",
    "        返回 = [-1]*n\n",
    "        for i in range(k, n-k):\n",
    "            k数组和 += nums[i+k]\n",
    "            返回[i] = k数组和//K\n",
    "            k数组和 -= nums[i-k]\n",
    "        return 返回\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        K = k*2+1\n",
    "        返回 = [-1]*n\n",
    "        if n < K:\n",
    "            return 返回\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[i] += nums[i-1]\n",
    "        返回[k] = nums[k+k]//K\n",
    "        for i in range(k+1, n-k):\n",
    "            返回[i] = (nums[i+k] - nums[i-k-1])//K\n",
    "        return 返回\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        K = k*2+1\n",
    "        返回 = [-1]*n\n",
    "        if n < K:\n",
    "            return 返回\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[i] += nums[i-1]\n",
    "        返回[k] = nums[k+k]//K\n",
    "        for i in range(k+1, n-k):\n",
    "            返回[i] = (nums[i+k] - nums[i-k-1])//K\n",
    "        return 返回\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        ans = []\n",
    "        temp = 0\n",
    "        if 2 * k < len(nums):\n",
    "            for i in range(2 * k):\n",
    "                temp += nums[i]\n",
    "            for i in range(2 * k, len(nums)):\n",
    "                temp += nums[i]\n",
    "                print(temp)\n",
    "                ans.append(temp // (2 * k + 1))\n",
    "                temp -= nums[i - 2 * k]\n",
    "            return [-1] * k + ans + [-1] * k\n",
    "        else:\n",
    "            return [-1] * len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        n = len(nums)\n",
    "        ans = [-1] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            left = i - k\n",
    "            right = i + k\n",
    "            if 0 <= left < n and 0 <= right < n:\n",
    "                ans[i] = (pre[right+1] - pre[left]) // (2*k+1)\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAverages(self, nums: List[int], k: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i + 1] = pre[i] + nums[i]\n",
    "        ans = [-1] * n\n",
    "        for i in range(n):\n",
    "            if i - k >= 0 and i + k < n:\n",
    "                ans[i] = (pre[i + k + 1] - pre[i - k])//(2*k + 1)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
